// https://leetcode.cn/problems/simplify-path/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用栈结构处理路径字符串
// 2. 按'/'分割路径，处理每个目录单元
// 3. 遇到"."或空字符串跳过，遇到".."弹出栈顶
// 4. 其他有效目录名压入栈中
// 5. 最后将栈中目录用'/'连接生成规范路径
// 6. 时间复杂度：O(N)，空间复杂度：O(N)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include <sstream>

class Solution 
{
public:
    string simplifyPath(string path) 
    {
        vector<string> stack;

        istringstream ss(path);
        string word;
        while (getline(ss, word, '/'))
        {
            if (word.empty() || word == ".")
            {
                continue;
            }
            else if (word != "..")
            {
                stack.push_back(word);
            }
            else if (!stack.empty())
            {
                stack.pop_back();
            }
        }

        string res;
        res += '/';
        for (const string& str : stack)
        {
            res += str;
            res += '/';
        }
        res.pop_back();

        return res.empty() ? "/" : res;
    }
};

int main()
{
    string path1 = "/home/", path2= "/home//foo/", path3 = "/home/user/Documents/../Pictures";
    Solution sol;

    cout << sol.simplifyPath(path1) << endl;
    cout << sol.simplifyPath(path2) << endl;
    cout << sol.simplifyPath(path3) << endl;

    return 0;
}